package com.hardy.leecode;

/**
 * Author: Hardy
 * Date:   2020/6/27
 * Description:
 * - 缺失的第一个正数
 * 给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [1,2,0]
 * 输出: 3
 * 示例 2:
 * <p>
 * 输入: [3,4,-1,1]
 * 输出: 2
 * 示例 3:
 * <p>
 * 输入: [7,8,9,11,12]
 * 输出: 1
 * <p>
 * 提示：
 * 你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。
 * <p>
 * 链接：https://leetcode-cn.com/problems/first-missing-positive
 * <p>
 * - 思路: 数组nums中的'值'转换为数组'下标', 同事保留元数据, 关系: 值->[1, n], 下标->[0, n-1]
 * 假设: nums[1,2,5,4,3] 数组内值是连续，那么如果把'值'转换为'下标'处理，必定会找到一对一对应
 * 假设: nums[1,2,6,4,3] 数组内值是不是连续，那么如果把'值'转换为'下标'处理，会发现4无法找对对应关系
 **/
public class Que41 {

    public static void main(String[] args) {
        int[] nums = new int[]{1, 1};

        System.out.println(new Solution().firstMissingPositive(nums));
    }

    static class Solution {

        public int firstMissingPositive(int[] nums) {
            int l = nums.length;

            for (int i = 0; i < l; i++) {
                // 属于 [1, n] && 不在标准位置 && 置换前后不相同
                while (nums[i] > 0 && nums[i] <= l && nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
                    int val = nums[i];
                    nums[i] = nums[val - 1];
                    nums[val - 1] = val;
                }
            }

            // 下标错位则找到值
            for (int i = 0; i < l; i++) {
                if (nums[i] != i + 1) return i + 1;
            }
            return l + 1;
        }
    }

    static class Solution2 {

        public int firstMissingPositive(int[] nums) {
            int l = nums.length;

            // 屏蔽 无需关系的数
            for (int i = 0; i < l; i++) {
                int val = nums[i];
                if (val <= 0 || val > l) nums[i] = l + 1;
            }

            // 转换标记(值找下标)
            for (int i = 0; i < l; i++) {
                int val = Math.abs(nums[i]);
                if (val > l) continue;
                nums[val - 1] = -Math.abs(nums[val - 1]); // 防止重复翻转
            }

            // 下标变成值，值变成下标
            for (int i = 0; i < l; i++) {
                if (nums[i] >= 0) return i + 1;
            }
            return l + 1;
        }
    }
}
